/*
 * Copyright 2013-2025 chronicle.software; SPDX-License-Identifier: Apache-2.0
 */
package net.openhft.hashing;

import org.junit.Assert;
import org.junit.Test;

import java.io.UnsupportedEncodingException;

import static net.openhft.hashing.CityAndFarmHash_1_1.K0;
import static org.junit.Assert.assertEquals;

/**
 * Based on https://github.com/google/farmhash/blob/34c13ddfab0e35422f4c3979f360635a8c050260/src/farmhash.cc
 */
public class OriginalFarmHashTest {
    private static final int kDataSize = 1 << 20;
    private static final int kTestSize = 300;
    private static final byte[] data = new byte[kDataSize];
    static {
        long a = 9;
        long b = 777;
        for (int i = 0; i < kDataSize; i++) {
            a += b;
            b += a;
            a = (a ^ (a >>> 41)) * K0;
            b = (b ^ (b >>> 41)) * K0 + i;
            byte u = (byte) (b >>> 37);
            data[i] = u;
        }
    }

    private static final int c1 = 0xcc9e2d51;

    private static long createSeed(int offset, int salt) {
        int h = salt;
        h = h * c1;
        h ^= (h >>> 17);
        h = h * c1;
        h ^= (h >>> 17);
        h = h * c1;
        h ^= (h >>> 17);
        h += offset;
        h = h * c1;
        h ^= (h >>> 17);
        h = h * c1;
        h ^= (h >>> 17);
        h = h * c1;
        h ^= (h >>> 17);
        return h & 0xFFFFFFFFL;
    }

    private static long SEED(int offset) {
        return createSeed(offset, -1);
    }

    private static long SEED0(int offset) {
        return createSeed(offset, 0);
    }

    private static long SEED1(int offset) {
        return createSeed(offset, 1);
    }

    @Test
    public void testNa() {
        int expectedIndex = 0, i = 0;
        for ( ; i < kTestSize - 1; i++) {
            expectedIndex = testNa(i * i, i, expectedIndex);
        }
        for ( ; i < kDataSize; i += i / 7) {
            expectedIndex = testNa(0, i, expectedIndex);
        }
        testNa(0, kDataSize, expectedIndex);
    }

    private static int testNa(int offset, int len, int expectedIndex) {
        LongHashFunction f = LongHashFunction.farmNa(SEED0(offset), SEED1(offset));
        long h = f.hashBytes(data, offset, len);
        assertEquals(NA_EXPECTED[expectedIndex++], h >>> 32);
        assertEquals(NA_EXPECTED[expectedIndex++], (h << 32) >>> 32);

        f = LongHashFunction.farmNa(SEED(offset));
        h = f.hashBytes(data, offset, len);
        assertEquals(NA_EXPECTED[expectedIndex++], h >>> 32);
        assertEquals(NA_EXPECTED[expectedIndex++], (h << 32) >>> 32);

        f = LongHashFunction.farmNa();
        h = f.hashBytes(data, offset, len);
        assertEquals(NA_EXPECTED[expectedIndex++], h >>> 32);
        assertEquals(NA_EXPECTED[expectedIndex++], (h << 32) >>> 32);

        return expectedIndex;
    }

    @Test
    public void testUo() {
        int expectedIndex = 0, i = 0;
        for ( ; i < kTestSize - 1; i++) {
            expectedIndex = testUo(i * i, i, expectedIndex);
        }
        for ( ; i < kDataSize; i += i / 7) {
            expectedIndex = testUo(0, i, expectedIndex);
        }
        testUo(0, kDataSize, expectedIndex);
    }

    private static int testUo(int offset, int len, int expectedIndex) {
        LongHashFunction f = LongHashFunction.farmUo(SEED(offset));
        long h = f.hashBytes(data, offset, len);
        assertEquals(UO_EXPECTED[expectedIndex++], h >>> 32);
        assertEquals(UO_EXPECTED[expectedIndex++], (h << 32) >>> 32);

        f = LongHashFunction.farmUo();
        h = f.hashBytes(data, offset, len);
        assertEquals(UO_EXPECTED[expectedIndex++], h >>> 32);
        assertEquals(UO_EXPECTED[expectedIndex++], (h << 32) >>> 32);

        return expectedIndex;
    }

    @Test
    public void testUoGo() {
        for (Object[] g : GOLDEN_64) {
            long hash = (Long) g[0];
            try {
                byte[] s = ((String)g[1]).getBytes("US-ASCII");
                Assert.assertEquals(hash, LongHashFunction.farmUo().hashBytes(s));
            } catch (UnsupportedEncodingException e) {
                throw new RuntimeException(e);
            }
        }
    }

    private static final Object[][] GOLDEN_64 = {
            {0xb3454265b6df75e3L, "a"},
            {0xaa8d6e5242ada51eL, "ab"},
            {0x24a5b3a074e7f369L, "abc"},
            {0x1a5502de4a1f8101L, "abcd"},
            {0xc22f4663e54e04d4L, "abcde"},
            {0xc329379e6a03c2cdL, "abcdef"},
            {0x3c40c92b1ccb7355L, "abcdefg"},
            {0xfee9d22990c82909L, "abcdefgh"},
            {0x332c8ed4dae5ba42L, "abcdefghi"},
            {0x8a3abb6a5f3fb7fbL, "abcdefghij"},
            {0xe8f89ab6df9bdd25L, "Discard medicine more than two years old."},
            {0x786d7e1987023ca9L, "He who has a shady past knows that nice guys finish last."},
            {0xa9961670ce2a46d9L, "I wouldn't marry him with a ten foot pole."},
            {0x5d14f96c18fe3d5eL, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
            {0x2a578b80bb82147cL, "The days of the digital watch are numbered.  -Tom Stoppard"},
            {0x8eb3808d1ccfc779L, "Nepal premier won't resign."},
            {0xb8d104d1135bbc60L, "For every action there is an equal and opposite government program."},
            {0xec8848fd3b266c10L, "His money is twice tainted: 'taint yours and 'taint mine."},
            {0xfe6aa49558b3cbe0L, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
            {0xa104da6f2f575514L, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
            {0x80d73b843ba57db8L, "size:  a.out:  bad magic"},
            {0xc2f8db8624fefc0eL, "The major problem is with sendmail.  -Mark Horton"},
            {0xa58e3702193e4631L, "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
            {0xbdd69b798d6ba37aL, "If the enemy is within range, then so are you."},
            {0x61751a90ec7d71bfL, "It's well we cannot hear the screams/That we create in others' dreams."},
            {0x836f5ff0c2a7dfaaL, "You remind me of a TV show, but that's all right: I watch it anyway."},
            {0xb944f8a16261e414L, "C is as portable as Stonehedge!!"},
            {0x96d012f9bccb3eL, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
            {0x8fe4429d157f60f5L, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule"},
            {0x5a0a6efd52e84e2aL, "How can you write a big system without C++?  -Paul Glick"},
    };

    private static final long[] NA_EXPECTED = {
            1140953930L, 861465670L,
            3277735313L, 2681724312L,
            2598464059L, 797982799L,
            890626835L, 800175912L,
            2603993599L, 921001710L,
            1410420968L, 2134990486L,
            3283896453L, 1867689945L,
            2914424215L, 2244477846L,
            255297188L, 2992121793L,
            1110588164L, 4186314283L,
            161451183L, 3943596029L,
            4019337850L, 452431531L,
            283198166L, 2741341286L,
            3379021470L, 2557197665L,
            299850021L, 2532580744L,
            452473466L, 1706958772L,
            1298374911L, 3099673830L,
            2199864459L, 3696623795L,
            236935126L, 2976578695L,
            4055299123L, 3281581178L,
            1053458494L, 1882212500L,
            2305012065L, 2169731866L,
            3456121707L, 275903667L,
            458884671L, 3033004529L,
            3058973506L, 2379411653L,
            1898235244L, 1402319660L,
            2700149065L, 2699376854L,
            147814787L, 720739346L,
            2433714046L, 4222949502L,
            4220361840L, 1712034059L,
            3425469811L, 3690733394L,
            4148372108L, 1330324210L,
            594028478L, 2921867846L,
            1635026870L, 192883107L,
            780716741L, 1728752234L,
            3280331829L, 326029180L,
            3969463346L, 1436364519L,
            393215742L, 3349570000L,
            3824583307L, 1612122221L,
            2859809759L, 3808705738L,
            1379537552L, 1646032583L,
            2233466664L, 1432476832L,
            4023053163L, 2650381482L,
            2052294713L, 3552092450L,
            1628777059L, 1499109081L,
            3476440786L, 3829307897L,
            2960536756L, 1554038301L,
            1145519619L, 3190844552L,
            2902102606L, 3600725550L,
            237495366L, 540224401L,
            65721842L, 489963606L,
            1448662590L, 397635823L,
            1596489240L, 1562872448L,
            1790705123L, 2128624475L,
            180854224L, 2604346966L,
            1435705557L, 1262831810L,
            155445229L, 1672724608L,
            1669465176L, 1341975128L,
            663607706L, 2077310004L,
            3610042449L, 1911523866L,
            1043692997L, 1454396064L,
            2563776023L, 294527927L,
            1099072299L, 1389770549L,
            703505868L, 678706990L,
            2952353448L, 2026137563L,
            3603803785L, 629449419L,
            1933894405L, 3043213226L,
            226132789L, 2489287368L,
            1552847036L, 645684964L,
            3828089804L, 3632594520L,
            187883449L, 230403464L,
            3151491850L, 3272648435L,
            3729087873L, 1303930448L,
            2002861219L, 165370827L,
            916494250L, 1230085527L,
            3103338579L, 3064290191L,
            3807265751L, 3628174014L,
            231181488L, 851743255L,
            2295806711L, 1781190011L,
            2988893883L, 1554380634L,
            1142264800L, 3667013118L,
            1968445277L, 315203929L,
            2638023604L, 2290487377L,
            732137533L, 1909203251L,
            440398219L, 1891630171L,
            1380301172L, 1498556724L,
            4072067757L, 4165088768L,
            4204318635L, 441430649L,
            3931792696L, 197618179L,
            956300927L, 914413116L,
            3010839769L, 2837339569L,
            2148126371L, 1913303225L,
            3074915312L, 3117299654L,
            4139181436L, 2993479124L,
            3178848746L, 1357272220L,
            1438494951L, 507436733L,
            667183474L, 2084369203L,
            3854939912L, 1413396341L,
            126024219L, 146044391L,
            1016656857L, 3022024459L,
            3254014218L, 429095991L,
            165589978L, 1578546616L,
            985653208L, 1718653828L,
            623071693L, 366414107L,
            249776086L, 1207522198L,
            3047342438L, 2991127487L,
            3120876698L, 1684583131L,
            46987739L, 1157614300L,
            863214540L, 1087193030L,
            199124911L, 520792961L,
            3614377032L, 586863115L,
            3331828431L, 1013201099L,
            1716848157L, 4033596884L,
            1164298657L, 4140791139L,
            1146169032L, 1434258493L,
            3824360466L, 3242407770L,
            3725511003L, 232064808L,
            872586426L, 762243036L,
            2736953692L, 816692935L,
            512845449L, 3748861010L,
            2266795890L, 3781899767L,
            4290630595L, 517646945L,
            22638523L, 648000590L,
            959214578L, 558910384L,
            1283799121L, 3047062993L,
            1024246061L, 4027776454L,
            3544509313L, 622325861L,
            834785312L, 382936554L,
            411505255L, 1973395102L,
            1825135056L, 2725923798L,
            580988377L, 2826990641L,
            3474970689L, 1029055034L,
            812546227L, 2506885666L,
            2584372201L, 1758123094L,
            589567754L, 325737734L,
            345313518L, 2022370576L,
            3886113119L, 3338548567L,
            257578986L, 3698087965L,
            1776047957L, 1771384107L,
            3604937815L, 3198590202L,
            2305332220L, 191910725L,
            4232136669L, 427759438L,
            4244322689L, 542201663L,
            3315355162L, 2135941665L,
            556609672L, 45845311L,
            1175961330L, 3948351189L,
            23075771L, 3252374102L,
            1634635545L, 4151937410L,
            713127376L, 1467786451L,
            663013031L, 3444053918L,
            2638154051L, 810082938L,
            3077742128L, 1062268187L,
            2115441882L, 4081398201L,
            3735739145L, 2794294783L,
            2335576331L, 2560479831L,
            1379288194L, 4225182569L,
            2442302747L, 3948961926L,
            3958366652L, 3067277639L,
            3667516477L, 1709989541L,
            1516711748L, 2339636583L,
            4188504038L, 59581167L,
            2725013602L, 3639843023L,
            2658147000L, 2643979752L,
            3758739543L, 4189944477L,
            2470483982L, 877580602L,
            2995362413L, 118817200L,
            3252925478L, 2062343506L,
            3981838403L, 3762572073L,
            1231633714L, 4168280671L,
            2931588131L, 3284356565L,
            1129162571L, 732225574L,
            4173605289L, 1407328702L,
            1677744031L, 3532596884L,
            3232041815L, 1652884780L,
            2256541290L, 3459463480L,
            3740979556L, 259034107L,
            2227121257L, 1426140634L,
            3606709555L, 3424793077L,
            315836068L, 3200749877L,
            1386256573L, 24035717L,
            2982018998L, 1811050648L,
            234531934L, 1115203611L,
            1598686658L, 3146815575L,
            1603559457L, 323296368L,
            2632963283L, 1778459926L,
            739944537L, 579625482L,
            3486330348L, 492621815L,
            1231665285L, 2457048126L,
            3903349120L, 389846205L,
            3355404249L, 3275550588L,
            1052645068L, 862072556L,
            2834153464L, 1481069623L,
            2657392572L, 4279236653L,
            1688445808L, 701920051L,
            3740748788L, 3388062747L,
            1873358321L, 2152785640L,
            883382081L, 1005815394L,
            1020177209L, 734239551L,
            2371453141L, 100326520L,
            3488500412L, 1279682138L,
            2610427744L, 49703572L,
            3026361211L, 605900428L,
            302392721L, 2509302188L,
            1416453607L, 2815915291L,
            1862819968L, 519710058L,
            2450888314L, 4017598378L,
            937074653L, 3035635454L,
            1590230729L, 3268013438L,
            2710029305L, 12886044L,
            3711259084L, 2627383582L,
            3895772404L, 648534979L,
            260307902L, 855990313L,
            3669691805L, 263366740L,
            2938543471L, 414331688L,
            3080542944L, 3405007814L,
            3565059103L, 1190977418L,
            390836981L, 1606450012L,
            2649808239L, 2514169310L,
            2747519432L, 4129538640L,
            1721522849L, 492099164L,
            792990594L, 3625507637L,
            2271095827L, 2993032712L,
            2302363854L, 4013112951L,
            1111617969L, 2183845740L,
            795918276L, 1116991810L,
            3110898804L, 3963062126L,
            2737064702L, 462795667L,
            937372240L, 1343017609L,
            1091041189L, 2790555455L,
            277024217L, 25485284L,
            1166522068L, 1623631848L,
            241727183L, 2836158787L,
            3112996740L, 573836428L,
            2721658101L, 1937681565L,
            4175169209L, 3190765433L,
            1970000788L, 1668258120L,
            114616703L, 954762543L,
            199237753L, 4094644498L,
            2522281978L, 732086117L,
            1756889687L, 2936126607L,
            2437031370L, 4103143808L,
            3883389541L, 3171090854L,
            2483004780L, 1927385370L,
            2360538162L, 2740855009L,
            4241185118L, 1492209542L,
            1672737098L, 2148675559L,
            1789864670L, 2434313103L,
            2319172611L, 2760941207L,
            2636210123L, 1338083267L,
            1128080590L, 822806371L,
            1199583556L, 314727461L,
            1335160250L, 2084630531L,
            1156261526L, 316766066L,
            112090465L, 3129033323L,
            2746885618L, 636616055L,
            2582210744L, 1721064910L,
            3468394263L, 470463518L,
            2076016059L, 408721884L,
            2121041886L, 378460278L,
            1915948002L, 357324860L,
            2301682622L, 2691859523L,
            1869756364L, 2429314418L,
            2193146527L, 1185564327L,
            2614088922L, 1975527044L,
            919067651L, 2855948894L,
            3662539576L, 1943802836L,
            3529473373L, 1490330107L,
            366036094L, 3384241033L,
            4276268604L, 448403661L,
            4271796078L, 1910401882L,
            3077107698L, 299427366L,
            2035665349L, 3201262636L,
            3738454258L, 2554452696L,
            3588997135L, 3363895827L,
            1267505995L, 1852004679L,
            2237827073L, 2803250686L,
            3468044908L, 2143572850L,
            1728158656L, 1022551180L,
            1996680960L, 839529273L,
            2400647871L, 2201096054L,
            3606433628L, 2597259793L,
            3544595875L, 3909443124L,
            819278607L, 3447346709L,
            806136613L, 2711436388L,
            3656063205L, 837475154L,
            694525336L, 4070212073L,
            4011303412L, 1068395209L,
            438095290L, 484603494L,
            2673730227L, 737767009L,
            642310823L, 3914002299L,
            308425103L, 268427550L,
            1334387085L, 4069797497L,
            4280783219L, 2914011058L,
            4243643405L, 2849988118L,
            2504230175L, 1817156623L,
            2804200483L, 3406991497L,
            2948254999L, 2102063419L,
            1071272117L, 514889942L,
            571972433L, 1246595599L,
            1735616066L, 1539151988L,
            1230831543L, 277987182L,
            4269526481L, 991511607L,
            95237878L, 2005032160L,
            1291113144L, 626619670L,
            3560835907L, 164940926L,
            1433635018L, 116647396L,
            3039097112L, 2868163232L,
            1141645918L, 1764165478L,
            881378302L, 2159170082L,
            2953647681L, 1011320066L,
            184856151L, 1723308975L,
            336034862L, 2017579106L,
            1476681709L, 147523618L,
            3896252223L, 2264728166L,
            944743644L, 1694443528L,
            2690700128L, 1947321519L,
            735478508L, 4058183171L,
            260177668L, 505662155L,
            2391691262L, 1920739747L,
            3216960415L, 1898176786L,
            3722741628L, 1511077569L,
            449636564L, 983350414L,
            2580237367L, 2055059789L,
            1103819072L, 2089123665L,
            3873755579L, 2718467458L,
            3124338704L, 3204250304L,
            2475035432L, 1120017626L,
            3873758287L, 1982999824L,
            2950794582L, 780634378L,
            2842141483L, 4029205195L,
            1656892865L, 3330993377L,
            80890710L, 1953796601L,
            3873078673L, 136118734L,
            2317676604L, 4199091610L,
            1864448181L, 3063437608L,
            1699452298L, 1403506686L,
            1513069466L, 2348491299L,
            4273657745L, 4055855649L,
            1805475756L, 2562064338L,
            973124563L, 4197091358L,
            172861513L, 2858726767L,
            4271866024L, 3071338162L,
            3590386266L, 2328277259L,
            1096050703L, 1189614342L,
            459509140L, 771592405L,
            817999971L, 3740825152L,
            520400189L, 1941874618L,
            185232757L, 4032960199L,
            3928245258L, 3527721294L,
            1301118856L, 752188080L,
            3512945009L, 308584855L,
            2105373972L, 752872278L,
            3823368815L, 3760952096L,
            4250142168L, 2565680167L,
            3646354146L, 1259957455L,
            1085857127L, 3471066607L,
            38924274L, 3770488806L,
            1083869477L, 3312508103L,
            71956383L, 3738784936L,
            3099963860L, 1255084262L,
            4286969992L, 3621849251L,
            1190908967L, 1831557743L,
            2363435042L, 54945052L,
            4059585566L, 4023974274L,
            1788578453L, 3442180039L,
            2534883189L, 2432427547L,
            3909757989L, 731996369L,
            4168347425L, 1356028512L,
            2741583197L, 1280920000L,
            312887059L, 3259015297L,
            3946278527L, 4135481831L,
            1281043691L, 1121403845L,
            3312292477L, 1819941269L,
            1741932545L, 3293015483L,
            2127558730L, 713121337L,
            2635469238L, 486003418L,
            4015067527L, 2976737859L,
            2108187161L, 927011680L,
            1970188338L, 4177613234L,
            1799789551L, 2118505126L,
            4134691985L, 1958963937L,
            1929210029L, 2555835851L,
            2768832862L, 910892050L,
            2567532373L, 4075249328L,
            86689814L, 3726640307L,
            1392137718L, 1240000030L,
            4104757832L, 3026358429L,
            313797689L, 1435798509L,
            3101500919L, 1241665335L,
            3573008472L, 3615577014L,
            3767659003L, 3134294021L,
            4063565523L, 2296824134L,
            1541946015L, 3087190425L,
            2693152531L, 2199672572L,
            2123763822L, 1034244398L,
            857839960L, 2515339233L,
            2228007483L, 1628096047L,
            2116502287L, 2502657424L,
            2809830736L, 460237542L,
            450205998L, 3646921704L,
            3818199357L, 1808504491L,
            1950698961L, 2069753399L,
            3657033172L, 3734547671L,
            4067859590L, 3292597295L,
            1106466069L, 356742959L,
            2469567432L, 3495418823L,
            183440071L, 3248055817L,
            3662626864L, 1750561299L,
            3926138664L, 4088592524L,
            567122118L, 3810297651L,
            992181339L, 3384018814L,
            3272124369L, 3177596743L,
            320086295L, 2316548367L,
            100741310L, 451656820L,
            4086604273L, 3759628395L,
            2553391092L, 1745659881L,
            3650357479L, 2390172694L,
            330172533L, 767377322L,
            526742034L, 4102497288L,
            2088767754L, 164402616L,
            2482632320L, 2352347393L,
            1873658044L, 3861555476L,
            2751052984L, 1767810825L,
            20037241L, 545143220L,
            2594532522L, 472304191L,
            3441135892L, 3323383489L,
            258785117L, 2977745165L,
            2781737565L, 2963590112L,
            2756998822L, 207428029L,
            2581558559L, 3824717027L,
            1258619503L, 3472047571L,
            2648427775L, 2360400900L,
            2393763818L, 2332399088L,
            3932701729L, 884421165L,
            1396468647L, 1377764574L,
            4061795938L, 1559119087L,
            3343596838L, 3604258095L,
            1435134775L, 1099809675L,
            908163739L, 1418405656L,
            368446627L, 3741651161L,
            3374512975L, 3542220540L,
            3244772570L, 200009340L,
            3198975081L, 2521038253L,
            4081637863L, 337070226L,
            3235259030L, 3897262827L,
            736956644L, 641040550L,
            644850146L, 1306761320L,
            4219448634L, 193750500L,
            3293278106L, 1383997679L,
            1242645122L, 4109252858L,
            450747727L, 3716617561L,
            362725793L, 2252520167L,
            3377483696L, 1788337208L,
            8130777L, 3226734120L,
            759239140L, 1012411364L,
            1658628529L, 2911512007L,
            1002580201L, 1681898320L,
            3039016929L, 4294520281L,
            367022558L, 3071359622L,
            3205848570L, 152989999L,
            3839042136L, 2357687350L,
            4273132307L, 3898950547L,
            1176841812L, 1314157485L,
            75443951L, 1027027239L,
            1858986613L, 2040551642L,
            36574105L, 2603059541L,
            3456147251L, 2137668425L,
            4077477194L, 3565689036L,
            491832241L, 363703593L,
            2579177168L, 3589545214L,
            265993036L, 1864569342L,
            4149035573L, 3189253455L,
            1072259310L, 3153745937L,
            923017956L, 490608221L,
            855846773L, 845706553L,
            1018226240L, 1604548872L,
            3833372385L, 3287246572L,
            2757959551L, 2452872151L,
            1553870564L, 1713154780L,
            2649450292L, 500120236L,
            84251717L, 661869670L,
            1444911517L, 2489716881L,
            2810524030L, 1561519055L,
            3884088359L, 2509890699L,
            4247155916L, 1005636939L,
            3224066062L, 2774151984L,
            2035978240L, 2514910366L,
            1478837908L, 3144450144L,
            2107011431L, 96459446L,
            3587732908L, 2389230590L,
            3287635953L, 250533792L,
            1235983679L, 4237425634L,
            3704645833L, 3882376657L,
            2976369049L, 1187061987L,
            276949224L, 4100839753L,
            1698347543L, 1629662314L,
            1556151829L, 3784939568L,
            427484362L, 4246879223L,
            3155311770L, 4285163791L,
            1693376813L, 124492786L,
            1858777639L, 3476334357L,
            1941442701L, 1121980173L,
            3485932087L, 820852908L,
            358032121L, 2511026735L,
            1873607283L, 2556067450L,
            2248275536L, 1528632094L,
            1535473864L, 556796152L,
            1499201704L, 1472623890L,
            1526518503L, 3692729434L,
            1476438092L, 2913077464L,
            335109599L, 2167614601L,
            4121131078L, 3158127917L,
            3051522276L, 4046477658L,
            2857717851L, 1863977403L,
            1341023343L, 692059110L,
            1802040304L, 990407433L,
            3285847572L, 319814144L,
            561105582L, 1540183799L,
            4052924496L, 2926590471L,
            2244539806L, 439121871L,
            3317903224L, 3178387550L,
            4265214507L, 82077489L,
            1978918971L, 4279668976L,
            128732476L, 2853224222L,
            464407878L, 4190838199L,
            997819001L, 3250520802L,
            2330081301L, 4095846095L,
            733509243L, 1583801700L,
            722314527L, 3552883023L,
            1403784280L, 432327540L,
            1877837196L, 3912423882L,
            505219998L, 696031431L,
            908238873L, 4189387259L,
            8759461L, 2540185277L,
            3385159748L, 381355877L,
            2519951681L, 1679786240L,
            2019419351L, 4051584612L,
            1933923923L, 3768201861L,
            1670133081L, 3454981037L,
            700836153L, 1675560450L,
            371560700L, 338262316L,
            847351840L, 2222395828L,
            3130433948L, 405251683L,
            3037574880L, 184098830L,
            453340528L, 1385561439L,
            2224044848L, 4071581802L,
            1431235296L, 5570097L,
            570114376L, 2287305551L,
            2272418128L, 803575837L,
            3943113491L, 414959787L,
            708083137L, 2452657767L,
            4019147902L, 3841480082L,
            3791794715L, 2965956183L,
            2763690963L, 2350937598L,
            3424361375L, 779434428L,
            1274947212L, 686105485L,
            3426668051L, 3692865672L,
            3057021940L, 2285701422L,
            349809124L, 1379278508L,
            3623750518L, 215970497L,
            1783152480L, 823305654L,
            216118434L, 1787189830L,
            3692048450L, 2272612521L,
            3032187389L, 4159715581L,
            1388133148L, 1611772864L,
            2544383526L, 552925303L,
            3420960112L, 3198900547L,
            3503230228L, 2603352423L,
            2318375898L, 4064071435L,
            3006227299L, 4194096960L,
            1283392422L, 1510460996L,
            174272138L, 3671038966L,
            1775955687L, 1719108984L,
            1763892006L, 1385029063L,
            4083790740L, 406757708L,
            684087286L, 531310503L,
            3329923157L, 3492083607L,
            1059031410L, 3037314475L,
            3105682208L, 3382290593L,
            2292208503L, 426380557L,
            97373678L, 3842309471L,
            777173623L, 3241407531L,
            303065016L, 1477104583L,
            4234905200L, 2512514774L,
            2649684057L, 1397502982L,
            1802596032L, 3973022223L,
            2543566442L, 3139578968L,
            3193669211L, 811750340L,
            4013496209L, 567361887L,
            4169410406L, 3622282782L,
            3403136990L, 2540585554L,
            895210040L, 3862229802L,
            1145435213L, 4146963980L,
            784952939L, 943914610L,
            573034522L, 464420660L,
            2356867109L, 3054347639L,
            3985088434L, 1911188923L,
            583391304L, 176468511L,
            2990150068L, 2338031599L,
            519948041L, 3181425568L,
            496106033L, 4110294665L,
            2736756930L, 1196757691L,
            1089679033L, 240953857L,
            3399092928L, 4040779538L,
            2843673626L, 240495962L,
            3017658263L, 3828377737L,
            4243717901L, 2448373688L,
            2759616657L, 2246245780L,
            308018483L, 4262383425L,
            2731780771L, 328023017L,
            2884443148L, 841480070L,
            3188015819L, 4051263539L,
            2298178908L, 2944209234L,
            1372958390L, 4164532914L,
            4074952232L, 1683612329L,
            2155036654L, 1872815858L,
            2041174279L, 2368092311L,
            206775997L, 2283918569L,
            645945606L, 115406202L,
            4206471368L, 3923500892L,
            2217060665L, 350160869L,
            706531239L, 2824302286L,
            509981657L, 1469342315L,
            140980L, 1891558063L,
            164887091L, 3094962711L,
            3437115622L, 13327420L,
            422986366L, 330624974L,
            3630863408L, 2425505046L,
            824008515L, 3543885677L,
            918718096L, 376390582L,
            3224043675L, 3724791476L,
            1837192976L, 2968738516L,
            3424344721L, 3187805406L,
            1550978788L, 1743089918L,
            4251270061L, 645016762L,
            3855037968L, 1928519266L,
            1373803416L, 2289007286L,
            1889218686L, 1610271373L,
            3059200728L, 2108753646L,
            582042641L, 812347242L,
            3188172418L, 191994904L,
            1343511943L, 2247006571L,
            463291708L, 2697254095L,
            1534175504L, 1106275740L,
            622521957L, 917121602L,
            4095777215L, 3955972648L,
            3852234638L, 2845309942L,
            3299763344L, 2864033668L,
            2554947496L, 799569078L,
            2551629074L, 1102873346L,
            2661022773L, 2006922227L,
            2900438444L, 1448194126L,
            1321567432L, 1983773590L,
            1237256330L, 3449066284L,
            1691553115L, 3274671549L,
            4271625619L, 2741371614L,
            3285899651L, 786322314L,
            1586632825L, 564385522L,
            2530557509L, 2974240289L,
            1244759631L, 3263135197L,
            3592389776L, 3570296884L,
            2749873561L, 521432811L,
            987586766L, 3206261120L,
            1327840078L, 4078716491L,
            1753812954L, 976892272L,
            1827135136L, 1781944746L,
            1328622957L, 1015377974L,
            3439601008L, 2209584557L,
            2482286699L, 1109175923L,
            874877499L, 2036083451L,
            483570344L, 1091877599L,
            4190721328L, 1129462471L,
            640035849L, 1867372700L,
            920761165L, 3273688770L,
            1623777358L, 3389003793L,
            3241132743L, 2734783008L,
            696674661L, 2502161880L,
            1646071378L, 1164309901L,
            350411888L, 1978005963L,
            2253937037L, 7371540L,
            989577914L, 3626554867L,
            3214796883L, 531343826L,
            398899695L, 1145247203L,
            1516846461L, 3656006011L,
            529303412L, 3318455811L,
            3062828129L, 1696355359L,
            3698796465L, 3155218919L,
            1457595996L, 3191404246L,
            1395609912L, 2917345728L,
            1237411891L, 1854985978L,
            1091884675L, 3504488111L,
            3109924189L, 1628881950L,
            3939149151L, 878608872L,
            778235395L, 1052990614L,
            903730231L, 2069566979L,
            2437686324L, 3163786257L,
            2257884264L, 2123173186L,
            939764916L, 2933010098L,
            1235300371L, 1256485167L,
            1950274665L, 2180372319L,
            2648400302L, 122035049L,
            1883344352L, 2083771672L,
            3712110541L, 321199441L,
            1896357377L, 508560958L,
            3066325351L, 2770847216L,
            3177982504L, 296902736L,
            1486926688L, 456842861L,
            601221482L, 3992583643L,
            2794121515L, 1533934172L,
            1706465470L, 4281971893L,
            2557027816L, 900741486L,
            227175484L, 550595824L,
            690918144L, 2825943628L,
            90375300L, 300318232L,
            1985329734L, 1440763373L,
            3670603707L, 2533900859L,
            3253901179L, 542270815L,
            3677388841L, 307706478L,
            2570910669L, 3320103693L,
            1273768482L, 1216399252L,
            1652924805L, 1043647584L,
            1120323676L, 639941430L,
            325675502L, 3652676161L,
            4241680335L, 1545838362L,
            1991398008L, 4100211814L,
            1097584090L, 3262252593L,
            2254324292L, 1765019121L,
            4060211241L, 2315856188L,
            3704419305L, 411263051L,
            238929055L, 3540688404L,
            3094544537L, 3250435765L,
            3460621305L, 1967599860L,
            2016157366L, 847389916L,
            1659615591L, 4020453639L,
            901109753L, 2682611693L,
            1661364280L, 177155177L,
            3210561911L, 3802058181L,
            797089608L, 3286110054L,
            2110358240L, 1353279028L,
            2479975820L, 471725410L,
            2219863904L, 3623364733L,
            3167128228L, 1052188336L,
            3656587111L, 721788662L,
            3061255808L, 1615375832L,
            924941453L, 2547780700L,
            3328169224L, 1310964134L,
            2701956286L, 4145497671L,
            1421461094L, 1221397398L,
            1589183618L, 1492533854L,
            449740816L, 2686506989L,
            3035198924L, 1682886232L,
            2529760244L, 3342031659L,
            1235084019L, 2151665147L,
            2315686577L, 3282027660L,
            1140138691L, 2754346599L,
            2091754612L, 1178454681L,
            4226896579L, 2942520471L,
            2122168506L, 3751680858L,
            3213794286L, 2601416506L,
            4142747914L, 3951404257L,
            4243249649L, 748595836L,
            4004834921L, 238887261L,
            1927321047L, 2217148444L,
            205977665L, 1885975275L,
            186020771L, 2367569534L,
            2941662631L, 2608559272L,
            3342096731L, 741809437L,
            1962659444L, 3539886328L,
            3036596491L, 2282550094L,
            2366462727L, 2748286642L,
            2144472852L, 1390394371L,
            1257385924L, 2205425874L,
            2119055686L, 46865323L,
            3597555910L, 3188438773L,
            2372320753L, 3641116924L,
            3116286108L, 2680722658L,
            3371014971L, 2058751609L,
            2966943726L, 2345078707L,
            2330535244L, 4013841927L,
            1169588594L, 857915866L,
            1875260989L, 3175831309L,
            3193475664L, 1955181430L,
            923161569L, 4068653043L,
            776445899L, 954196929L,
            61509556L, 4248237857L,
            3808667664L, 581227317L,
            2893240187L, 4159497403L,
            4212264930L, 3973886195L,
            2077539039L, 851579036L,
            2957587591L, 772351886L,
            1173659554L, 946748363L,
            2794103714L, 2094375930L,
            4234750213L, 3671645488L,
            2614250782L, 2620465358L,
            3122317317L, 2365436865L,
            3393973390L, 523513960L,
            3645735309L, 2766686992L,
            2023960931L, 2312244996L,
            1875932218L, 3253711056L,
            3622416881L, 3274929205L,
            612094988L, 1555465129L,
            2114270406L, 3553762793L,
            1832633644L, 1087551556L,
            3306195841L, 1702313921L,
            3675066046L, 1735998785L,
            1690923980L, 1482649756L,
            1171351291L, 2043136409L,
            1962596992L, 461214626L,
            3278253346L, 1392428048L,
            3744621107L, 1028502697L,
            3991171462L, 1014064003L,
            3642345425L, 3186995039L,
            6114625L, 3359104346L,
            414856965L, 2814387514L,
            3583605071L, 2497896367L,
            1024572712L, 1927582962L,
            2892797583L, 845302635L,
            328548052L, 1523379748L,
            3392622118L, 1347167673L,
            1012316581L, 37767602L,
            2647726017L, 1070326065L,
            2075035198L, 4202817168L,
            2502924707L, 2612406822L,
            2187115553L, 1180137213L,
            701024148L, 1481965992L,
            3223787553L, 2083541843L,
            203230202L, 3876887380L,
            1334816273L, 2870251538L,
            2186205850L, 3985213979L,
            333533378L, 806507642L,
            1010064531L, 713520765L,
            3084131515L, 2637421459L,
            1703168933L, 1517562266L,
            4089081247L, 3231042924L,
            3079916123L, 3154574447L,
            2253948262L, 1725190035L,
            2452539325L, 1343734533L,
            213706059L, 2519409656L,
            108055211L, 2916327746L,
            587001593L, 1917607088L,
            4202913084L, 926304016L,
            469255411L, 4042080256L,
            3498936874L, 246692543L,
            495780578L, 438717281L,
            2259272650L, 4011324645L,
            2836854664L, 2317249321L,
            946828752L, 1280403658L,
            1905648354L, 2034241661L,
            774652981L, 1285694082L,
            2200307766L, 2158671727L,
            1135162148L, 232040752L,
            397012087L, 1717527689L,
            1720414106L, 918797022L,
            2580119304L, 3568069742L,
            2904461070L, 3893453420L,
            973817938L, 667499332L,
            3785870412L, 2088861715L,
            1565179401L, 600903026L,
            591806775L, 3512242245L,
            997964515L, 2339605347L,
            1134342772L, 3234226304L,
            4084179455L, 302315791L,
            2445626811L, 2590372496L,
            345572299L, 2274770442L,
            3600587867L, 3706939009L,
            1430507980L, 2656330434L,
            1079209397L, 2122849632L,
            1423705223L, 3826321888L,
            3683385276L, 1057038163L,
            1242840526L, 3987000643L,
            2398253089L, 1538190921L,
            1295898647L, 3570196893L,
            3065138774L, 3111336863L,
            2524949549L, 4203895425L,
            3025864372L, 968800353L,
            1023721001L, 3763083325L,
            526350786L, 635552097L,
            2308118370L, 2166472723L,
            2196937373L, 2643841788L,
            3040011470L, 4010301879L,
            2782379560L, 3474682856L,
            4201389782L, 4223278891L,
            1457302296L, 2251842132L,
            1090062008L, 3188219189L,
            292733931L, 1424229089L,
            1590782640L, 1365212370L,
            3975957073L, 3982969588L,
            2927147928L, 1048291071L,
            2766680094L, 884908196L,
            35237839L, 2221180633L,
            2490333812L, 4098360768L,
            4029081103L, 3490831871L,
            2392516272L, 3455379186L,
            3948800722L, 335456628L,
            2105117968L, 4181629008L,
            1044201772L, 3335754111L,
            540133451L, 3313113759L,
            3786107905L, 2627207327L,
            3540337875L, 3473113388L,
            3430536378L, 2514123129L,
            2124531276L, 3872633376L,
            3272957388L, 3501994650L,
            2418881542L, 487365389L,
            3877672368L, 1512866656L,
            3486531087L, 2102955203L,
            1136054817L, 3004241477L,
            1549075351L, 1302002008L,
            3936430045L, 2258587644L,
            4109233936L, 3679809321L,
            3467083076L, 2484463221L,
            1594979755L, 529218470L,
            3527024461L, 1147434678L,
            106799023L, 1823161970L,
            1704656738L, 1675883700L,
            3308746763L, 1875093248L,
            1352868568L, 1898561846L,
            2508994984L, 3177750780L,
            4217929592L, 400784472L,
            80090315L, 3564414786L,
            3841585648L, 3379293868L,
            160353261L, 2413172925L,
            2378499279L, 673436726L,
            1505702418L, 1330977363L,
            1853298225L, 3201741245L,
            2135714208L, 4069554166L,
            3715612384L, 3692488887L,
            3680311316L, 4274382900L,
            914186796L, 2264886523L,
            3869634032L, 1254199592L,
            1131020455L, 194781179L,
            429923922L, 2763792336L,
            2052895198L, 3997373194L,
            3440090658L, 2165746386L,
            1575500242L, 3463310191L,
            2064974716L, 3779513671L,
            3106421434L, 880320527L,
            3281914119L, 286569042L,
            3909096631L, 122359727L,
            1429837716L, 252230074L,
            4111461225L, 762273136L,
            93658514L, 2766407143L,
            3623657004L, 3869801679L,
            3925695921L, 2390397316L,
            2499025338L, 2741806539L,
            2507199021L, 1659221866L,
            361292116L, 4048761557L,
            3797133396L, 1517903247L,
            3121647246L, 3884308578L,
            1697201500L, 1558800262L,
            4150812360L, 3161302278L,
            2610217849L, 641564641L,
            183814518L, 2075245419L,
            611996508L, 2223461433L,
            329123979L, 121860586L,
            860985829L, 1137889144L,
            4018949439L, 2904348960L,
            947795261L, 1992594155L,
            4255427501L, 2281583851L,
            2892637604L, 1478186924L,
            3050771207L, 2767035539L,
            373510582L, 1963520320L,
            3763848370L, 3756817798L,
            627269409L, 1806905031L,
            1814444610L, 3646665053L,
            1822693920L, 278515794L,
            584050483L, 4142579188L,
            2149745808L, 3193071606L,
            1179706341L, 2693495182L,
            3259749808L, 644172091L,
            880509048L, 3340630542L,
            3365160815L, 2384445068L,
            3053081915L, 2840648309L,
            1986990122L, 1084703471L,
            2370410550L, 1627743573L,
            2244943480L, 4057483496L,
            2611595995L, 2470013639L,
            4024732359L, 3987190386L,
            873421687L, 2447660175L,
            3226583022L, 767655877L,
            2528024413L, 1962070688L,
            1233635843L, 2163464207L,
            659054446L, 854207134L,
            258410943L, 4197831420L,
            2515400215L, 3100476924L,
            1961549594L, 2219491151L,
            3997658851L, 163850514L,
            470325051L, 2598261204L,
            3052145580L, 59836528L,
            1376188597L, 966733415L,
            850667549L, 3622479237L,
            1083731990L, 1525777459L,
            4005126532L, 1428155540L,
            2781907007L, 943739431L,
            1493961005L, 2839096988L,
            2000057832L, 1941829603L,
            1901484772L, 939810041L,
            3377407371L, 3090115837L,
            3310840540L, 2068409688L,
            3261383939L, 2212130277L,
            2594774045L, 2912652418L,
            4179816101L, 3534504531L,
            3349254805L, 2796552902L,
            1385421283L, 4259908631L,
            3714780837L, 3070073945L,
            3372846298L, 3835884044L,
            3047965714L, 3009018735L,
            744091167L, 1861124263L,
            2764936304L, 1338171648L,
            4222019554L, 1395200692L,
            1371426007L, 3338031581L,
            2525665319L, 4196233786L,
            2332743921L, 1474702008L,
            2274266301L, 4255175517L,
            2290169528L, 1793910997L,
            2188254024L, 354202001L,
            3864458796L, 4280290498L,
            1554419340L, 1733094688L,
            2010552302L, 1561807039L,
            664313606L, 2548990879L,
            1084699349L, 3233936866L,
            973895284L, 2386881969L,
            1831995860L, 2961465052L,
            1428704144L, 3269904970L,
            231648253L, 2602483763L,
            4125013173L, 3319187387L,
            3347011944L, 1892898231L,
            4019114049L, 868879116L,
            4085937045L, 2378411019L,
            1072588531L, 3547435717L,
            2208070766L, 1069899078L,
            3142980597L, 2337088907L,
            1593338562L, 919414554L,
            688077849L, 3625708135L,
            1472447348L, 1947711896L,
            3953006207L, 877438080L,
            845995820L, 3150361443L,
            3053496713L, 2484577841L,
            224271045L, 2914958001L,
            2682612949L, 806655563L,
            2436224507L, 1907729235L,
            2920583824L, 1251814062L,
            2070814520L, 4034325578L,
            497847539L, 2714317144L,
            385182008L, 640855184L,
            1327075087L, 1062468773L,
            1757405994L, 1374270191L,
            4263183176L, 3041193150L,
            1037871524L, 3633173991L,
            4231821821L, 2830131945L,
            3505072908L, 2830570613L,
            4195208715L, 575398021L,
            3992840257L, 3691788221L,
            1949847968L, 2999344380L,
            3183782163L, 3723754342L,
            759716128L, 3284107364L,
            1714496583L, 15918244L,
            820509475L, 2553936299L,
            2201876606L, 4237151697L,
            2605688266L, 3253705097L,
            1008333207L, 712158730L,
            1722280252L, 1933868287L,
            4152736859L, 2097020806L,
            584426382L, 2836501956L,
            2522777566L, 1996172430L,
            2122199776L, 1069285218L,
            1474209360L, 690831894L,
            107482532L, 3695525410L,
            670591796L, 768977505L,
            2412057331L, 3647886687L,
            3110327607L, 1072658422L,
            379861934L, 1557579480L,
            4124127129L, 2271365865L,
            3880613089L, 739218494L,
            547346027L, 388559045L,
            3147335977L, 176230425L,
            3094853730L, 2554321205L,
            1495176194L, 4093461535L,
            3521297827L, 4108148413L,
            1913727929L, 1177947623L,
            1911655402L, 1053371241L,
            3265708874L, 1266515850L,
            1045540427L, 3194420196L,
            3717104621L, 1144474110L,
            1464392345L, 52070157L,
            4144237690L, 3350490823L,
            4166253320L, 2747410691L,
    };

    private static final long[] UO_EXPECTED = {
            3277735313L, 2681724312L,
            2598464059L, 797982799L,
            2603993599L, 921001710L,
            1410420968L, 2134990486L,
            2914424215L, 2244477846L,
            255297188L, 2992121793L,
            161451183L, 3943596029L,
            4019337850L, 452431531L,
            3379021470L, 2557197665L,
            299850021L, 2532580744L,
            1298374911L, 3099673830L,
            2199864459L, 3696623795L,
            4055299123L, 3281581178L,
            1053458494L, 1882212500L,
            3456121707L, 275903667L,
            458884671L, 3033004529L,
            1898235244L, 1402319660L,
            2700149065L, 2699376854L,
            2433714046L, 4222949502L,
            4220361840L, 1712034059L,
            4148372108L, 1330324210L,
            594028478L, 2921867846L,
            780716741L, 1728752234L,
            3280331829L, 326029180L,
            393215742L, 3349570000L,
            3824583307L, 1612122221L,
            1379537552L, 1646032583L,
            2233466664L, 1432476832L,
            2052294713L, 3552092450L,
            1628777059L, 1499109081L,
            2960536756L, 1554038301L,
            1145519619L, 3190844552L,
            237495366L, 540224401L,
            65721842L, 489963606L,
            1596489240L, 1562872448L,
            1790705123L, 2128624475L,
            1435705557L, 1262831810L,
            155445229L, 1672724608L,
            663607706L, 2077310004L,
            3610042449L, 1911523866L,
            2563776023L, 294527927L,
            1099072299L, 1389770549L,
            2952353448L, 2026137563L,
            3603803785L, 629449419L,
            226132789L, 2489287368L,
            1552847036L, 645684964L,
            187883449L, 230403464L,
            3151491850L, 3272648435L,
            2002861219L, 165370827L,
            916494250L, 1230085527L,
            3807265751L, 3628174014L,
            231181488L, 851743255L,
            2988893883L, 1554380634L,
            1142264800L, 3667013118L,
            2638023604L, 2290487377L,
            732137533L, 1909203251L,
            1380301172L, 1498556724L,
            4072067757L, 4165088768L,
            3931792696L, 197618179L,
            956300927L, 914413116L,
            2148126371L, 1913303225L,
            3074915312L, 3117299654L,
            3178848746L, 1357272220L,
            1438494951L, 507436733L,
            3854939912L, 1413396341L,
            126024219L, 146044391L,
            3254014218L, 429095991L,
            165589978L, 1578546616L,
            623071693L, 366414107L,
            249776086L, 1207522198L,
            3120876698L, 1684583131L,
            46987739L, 1157614300L,
            199124911L, 520792961L,
            3614377032L, 586863115L,
            1716848157L, 4033596884L,
            1164298657L, 4140791139L,
            3824360466L, 3242407770L,
            3725511003L, 232064808L,
            2736953692L, 816692935L,
            512845449L, 3748861010L,
            4290630595L, 517646945L,
            22638523L, 648000590L,
            1283799121L, 3047062993L,
            1024246061L, 4027776454L,
            834785312L, 382936554L,
            411505255L, 1973395102L,
            580988377L, 2826990641L,
            3474970689L, 1029055034L,
            2584372201L, 1758123094L,
            589567754L, 325737734L,
            3886113119L, 3338548567L,
            257578986L, 3698087965L,
            3604937815L, 3198590202L,
            2305332220L, 191910725L,
            4244322689L, 542201663L,
            3315355162L, 2135941665L,
            1175961330L, 3948351189L,
            23075771L, 3252374102L,
            713127376L, 1467786451L,
            663013031L, 3444053918L,
            3077742128L, 1062268187L,
            2115441882L, 4081398201L,
            2335576331L, 2560479831L,
            1379288194L, 4225182569L,
            3958366652L, 3067277639L,
            3667516477L, 1709989541L,
            4188504038L, 59581167L,
            2725013602L, 3639843023L,
            3758739543L, 4189944477L,
            2470483982L, 877580602L,
            3252925478L, 2062343506L,
            3981838403L, 3762572073L,
            2931588131L, 3284356565L,
            1129162571L, 732225574L,
            1677744031L, 3532596884L,
            3232041815L, 1652884780L,
            3740979556L, 259034107L,
            2227121257L, 1426140634L,
            315836068L, 3200749877L,
            1386256573L, 24035717L,
            234531934L, 1115203611L,
            1598686658L, 3146815575L,
            2632963283L, 1778459926L,
            739944537L, 579625482L,
            1231665285L, 2457048126L,
            3903349120L, 389846205L,
            1052645068L, 862072556L,
            2834153464L, 1481069623L,
            1688445808L, 701920051L,
            3740748788L, 3388062747L,
            1192588249L, 1410111809L,
            2633463887L, 4050419847L,
            2513844237L, 2187968410L,
            2951683019L, 3015806005L,
            3000537321L, 479241367L,
            252167538L, 1231057113L,
            393624922L, 704325635L,
            1467197045L, 2066433573L,
            3082385053L, 735688735L,
            956434529L, 4028590195L,
            4074716319L, 813690332L,
            2124740535L, 804073145L,
            3748881891L, 3195309868L,
            841856605L, 2585865274L,
            881504822L, 3254795114L,
            1241815736L, 970796142L,
            497175391L, 3929484338L,
            4264993211L, 1835322201L,
            3675707838L, 4205965408L,
            300298607L, 3858319990L,
            3255259608L, 4247675634L,
            1095823272L, 1197245408L,
            1742785722L, 785893184L,
            1702965674L, 850401405L,
            4084891412L, 1160134629L,
            2555998391L, 1972759056L,
            710625654L, 4116162021L,
            3352753742L, 85121177L,
            3513255468L, 2487440590L,
            2480032715L, 2287747045L,
            4090178629L, 4044418876L,
            1703944517L, 486290428L,
            1515601363L, 2011102035L,
            573985957L, 3536053779L,
            4257172787L, 576405853L,
            1523550693L, 1014952061L,
            711098718L, 2425317635L,
            3460807169L, 3688987163L,
            3167371443L, 3062418115L,
            3330028292L, 1713171303L,
            526177822L, 2602636307L,
            1245357025L, 3346699703L,
            254529415L, 4017058800L,
            1829738451L, 2164236533L,
            1381258384L, 4036354071L,
            1749181924L, 4118435443L,
            4130543625L, 688472265L,
            2731071299L, 2547657502L,
            4175776103L, 338058159L,
            3729582129L, 4181845558L,
            2227290760L, 146827036L,
            2459178427L, 1025353883L,
            4284109679L, 2502815838L,
            825124804L, 2533140036L,
            616327404L, 2448966429L,
            413992636L, 2334782461L,
            2239052397L, 1082330589L,
            3381164715L, 199381437L,
            2583939798L, 2848283092L,
            2300168091L, 2156336315L,
            1855234968L, 1982110346L,
            2482046810L, 3158163887L,
            2168864636L, 133643215L,
            3904021624L, 3646514568L,
            1176127003L, 4015671361L,
            100525019L, 3534706803L,
            2045051700L, 3452457457L,
            1492267772L, 2308393828L,
            3776661467L, 3281002516L,
            4246334524L, 743955039L,
            685631442L, 1147951686L,
            2040912376L, 2911148054L,
            3204999386L, 2415262714L,
            313209105L, 777065474L,
            2729416454L, 1029284767L,
            1632078298L, 1817552554L,
            3963877000L, 1919171906L,
            3843219958L, 3073580867L,
            865146997L, 2473524405L,
            2593817617L, 3643076308L,
            617975720L, 3671562289L,
            121812599L, 2902367378L,
            2260041112L, 1019936943L,
            320945955L, 2337845588L,
            1535670711L, 773792826L,
            3152195900L, 4090794518L,
            4142587430L, 484732447L,
            419191319L, 3377973345L,
            324924679L, 2809286837L,
            1562277603L, 1378362199L,
            3791551981L, 1097806406L,
            1386297408L, 2304900033L,
            3574135531L, 4017075736L,
            1161238398L, 1358056883L,
            3487080616L, 1516736273L,
            851615042L, 2927899494L,
            4077452507L, 2984955003L,
            3907754394L, 3578173844L,
            1948409509L, 1923531348L,
            3578472493L, 3710074193L,
            213811117L, 2586632018L,
            1922589216L, 274958014L,
            1654276320L, 2687561076L,
            2569061755L, 3122046057L,
            3203802620L, 1692079268L,
            477806878L, 140587742L,
            520565830L, 3674576684L,
            91246882L, 1010215946L,
            3703994407L, 69201295L,
            776213083L, 3677771507L,
            3696902571L, 3593730713L,
            2907901228L, 3239753796L,
            1586241476L, 1939595371L,
            2268396558L, 3468719670L,
            2955715987L, 2295501078L,
            2775848696L, 1358532390L,
            3843660102L, 82177963L,
            4094477877L, 191727221L,
            278661677L, 2889101923L,
            1352525614L, 2844977667L,
            1261140657L, 1747052377L,
            2334120653L, 645125282L,
            2707230761L, 4142246789L,
            1068639717L, 2288162940L,
            1419293714L, 1636932722L,
            3252686293L, 318543902L,
            2598802768L, 2025886508L,
            2250788464L, 2711763065L,
            255108733L, 1845587644L,
            3719270134L, 3940707863L,
            917608574L, 1363253259L,
            788659330L, 673256220L,
            109793386L, 341851980L,
            2698465479L, 3011229884L,
            3886713057L, 1276595523L,
            2439962760L, 2700515456L,
            205970448L, 4198897105L,
            875511891L, 371715572L,
            1033680610L, 4278599955L,
            3120038721L, 1256300069L,
            225629455L, 3735275001L,
            3961944123L, 1769389163L,
            1074553219L, 668829411L,
            1098679359L, 2573697509L,
            1885071395L, 4233785523L,
            2513878053L, 2030193788L,
            360256231L, 107312677L,
            310517502L, 2618936366L,
            3600462351L, 1216645846L,
            2970730323L, 4278812598L,
            94638678L, 1689811113L,
            4125738800L, 3103759730L,
            103797041L, 1397772514L,
            1669653333L, 572567964L,
            1612872497L, 2986430557L,
            214990655L, 3117607990L,
            1949717207L, 2260498180L,
            1493936866L, 3554860960L,
            1582022990L, 1263709570L,
            1244120487L, 3416600761L,
            224580012L, 4252610345L,
            286306391L, 814956796L,
            1820532305L, 2776960536L,
            3082703465L, 1659265982L,
            1157398049L, 3752806924L,
            3508246460L, 2902716664L,
            2110942730L, 3267551635L,
            902835431L, 405228165L,
            2341378668L, 2220373824L,
            3303626294L, 1175118221L,
            383517064L, 896322512L,
            1697257567L, 2202820683L,
            1837689083L, 1336556841L,
            914535232L, 3634083711L,
            1537187340L, 3712582785L,
            1088201893L, 3270984620L,
            3093195926L, 2561488770L,
            1962968100L, 236189500L,
            2549435227L, 536047554L,
            422609195L, 2958815818L,
            4166184983L, 3528794619L,
            1042329086L, 3914176886L,
            1359641525L, 1197100813L,
            1269739674L, 3301844628L,
            1831223342L, 3329594980L,
            2433669782L, 494908536L,
            1441714797L, 1174785921L,
            1933050423L, 958901065L,
            868981704L, 2163330264L,
            3243110680L, 1443133429L,
            1145009669L, 2520062970L,
            3851564853L, 2664619323L,
            2686075657L, 4042710240L,
            2125408249L, 4165697916L,
            2328730865L, 3160666939L,
            588683409L, 2126275847L,
            829404209L, 1878067032L,
            2567792910L, 897670516L,
            934312076L, 2952135524L,
            504832490L, 3312698056L,
            4015478120L, 1265237690L,
            3376133707L, 967674402L,
            1553513184L, 834830418L,
            2396504772L, 3278582098L,
            2950762705L, 4277111759L,
            4159211303L, 1290097509L,
            251949572L, 3065234219L,
            1832020534L, 312136369L,
            1103404394L, 198182691L,
            1369599600L, 3906710870L,
            2954651680L, 1535115487L,
            2389327507L, 1813520230L,
            632704095L, 140762681L,
            3123202913L, 3336005523L,
            1287729497L, 2198985327L,
            2470730783L, 3821758006L,
            1009870118L, 559702706L,
            4274686257L, 3187546567L,
            2402308151L, 1096697687L,
            678932329L, 3716363135L,
            2899950405L, 3046872820L,
            3754655641L, 2021741414L,
            1993425202L, 2185339100L,
            2838253700L, 3099212100L,
            1679617763L, 3703603898L,
            1135665833L, 3559875668L,
            2503579743L, 1446869792L,
            879818611L, 3788305533L,
            2879018745L, 2719373510L,
            3606051203L, 2166567748L,
            343595772L, 1996164093L,
            1577656121L, 475248376L,
            463852893L, 2864244470L,
            1332049663L, 3326459767L,
            3207234525L, 2028708916L,
            938916154L, 3115246264L,
            3272166407L, 557660441L,
            1265684026L, 245033807L,
            2440657523L, 255451671L,
            3811885130L, 1399880284L,
            1322855877L, 3452203069L,
            1324994449L, 3796404024L,
            2002090272L, 1568745354L,
            3700047753L, 31799506L,
            3009412313L, 3184047862L,
            728680761L, 3848624873L,
            1849329144L, 3160134214L,
            1272923193L, 1474278816L,
            1208883495L, 1566527339L,
            4136466541L, 630825649L,
            1717327230L, 1496132623L,
            2449386742L, 128106940L,
            2108574735L, 2584236470L,
            2872246579L, 397338552L,
            3088905079L, 3456882941L,
            1715915153L, 2940716269L,
            4168438718L, 467441309L,
            872996731L, 3206901319L,
            1610606159L, 2540270567L,
            1301658081L, 2379410194L,
            2109315753L, 3348545480L,
            2041927873L, 2644077493L,
            546596661L, 1017047954L,
            2596792972L, 2783958892L,
            2826408201L, 3531646869L,
            2219352672L, 4217451852L,
            1806867885L, 1903578924L,
            2076465705L, 2373061493L,
            1832925325L, 241574049L,
            1509517110L, 3703614272L,
            3429894862L, 3529565564L,
            4010000614L, 2256197939L,
            517086873L, 2964595704L,
            3501035294L, 4079457298L,
            1184683823L, 4260564140L,
            2339268412L, 3871564102L,
            1572637805L, 383233885L,
            3351411126L, 3419328182L,
            2017406667L, 919677938L,
            29804156L, 46276077L,
            3032591014L, 4204155962L,
            1172319502L, 969309871L,
            2211319468L, 4153726847L,
            3094193193L, 4240669441L,
            3441709766L, 1387233546L,
            4048882438L, 1217896566L,
            1580964938L, 740563169L,
            3691850348L, 3176426539L,
            2738323042L, 2948665536L,
            1474029445L, 3513354882L,
            3219466255L, 3799363969L,
            3961796122L, 1055550923L,
            1992212097L, 2263421398L,
            4289759174L, 2516844140L,
            1782515131L, 2746577402L,
            721928440L, 3529570984L,
            1705302106L, 768287270L,
            3474902815L, 4000011125L,
            3475618043L, 212490675L,
            549130471L, 2970128275L,
            3170016833L, 2549835613L,
            3691104824L, 2694324482L,
            4169365948L, 3738062408L,
            602930397L, 2148954730L,
            2636387819L, 2616619070L,
            301617872L, 374657036L,
            3862686086L, 431292293L,
            4225245165L, 1358580562L,
            2377363130L, 1415970351L,
            3885060756L, 1438379807L,
            2297418515L, 2954777083L,
            3970368221L, 1229801760L,
            1931934525L, 2287507921L,
            1713471510L, 2145608111L,
            2650140034L, 4081586725L,
            4196863572L, 1896558394L,
            4059852729L, 1813855658L,
            2618400836L, 1396056469L,
            2375584220L, 1037031473L,
            249284003L, 2450077637L,
            1383747654L, 3122687303L,
            2664431743L, 3855028730L,
            929335420L, 3193251135L,
            137313762L, 1850894384L,
            3163711272L, 3071568023L,
            418541677L, 3621223039L,
            340274176L, 1167681812L,
            4106647531L, 4022465625L,
            3069708839L, 2704165015L,
            2332023349L, 641449034L,
            921552000L, 1712976649L,
            1876484273L, 2343049860L,
            1834682077L, 4155949943L,
            2061821157L, 4240649383L,
            747285578L, 1626463554L,
            165503115L, 359629739L,
            3838102563L, 582664250L,
            3878924635L, 4117237498L,
            2250573853L, 804336148L,
            331393443L, 4242530387L,
            3346357270L, 1674051445L,
            3348019777L, 1722242971L,
            2509017299L, 2966108111L,
            4189102509L, 3323592310L,
            2631381069L, 4014551783L,
            4250787412L, 3448394212L,
            2664752123L, 3517585534L,
            3605365141L, 1669471183L,
            2210121140L, 760762191L,
            249697459L, 3416920106L,
            16322182L, 643179562L,
            1564226597L, 2134630675L,
            1011990087L, 2990167340L,
            2349550842L, 1642428946L,
            1214854475L, 2134299399L,
            2704221532L, 2104175211L,
            4283196353L, 1342880802L,
            198529755L, 2004468390L,
            2544665755L, 853593042L,
            2090611294L, 2970943872L,
            1472073141L, 850464484L,
            1407609278L, 3062461105L,
            366448238L, 3842907484L,
            488797416L, 1432670231L,
            294963924L, 3693536939L,
            3390549825L, 1583234720L,
            4032223840L, 2318423400L,
            2965642867L, 930822729L,
            1679099863L, 1728968857L,
            900822335L, 702309817L,
            3258354115L, 1502282913L,
            2811888503L, 3924947660L,
            2477280726L, 3651607391L,
            3788310204L, 1300369123L,
            1842333726L, 4146839064L,
            2468893861L, 4091095953L,
            488595746L, 1448097974L,
            1159634090L, 1738834113L,
            2928916831L, 4093725287L,
            530850094L, 291657799L,
            3548184546L, 679517009L,
            399175380L, 2658337143L,
            3827951761L, 3086277222L,
            2067718397L, 3632376023L,
            3553313841L, 119173722L,
            1702434637L, 1766260771L,
            895654784L, 751439914L,
            4008409498L, 215917713L,
            1288382231L, 2656990891L,
            2581779077L, 1570750352L,
            2666411616L, 3533987737L,
            4289478316L, 3576119563L,
            3869794273L, 963183826L,
            2081410737L, 3796810515L,
            1036883117L, 136547246L,
            875691100L, 2592925324L,
            2689342539L, 427154472L,
            532957601L, 1228758574L,
            1908591042L, 1464255968L,
            446980910L, 2984611177L,
            3508927906L, 2001585786L,
            2544767379L, 1525438381L,
            879448844L, 1348536411L,
            4242243590L, 2861338018L,
            601175800L, 764077711L,
            530635011L, 3785343245L,
            2378297261L, 457568934L,
            76438221L, 4104954272L,
            2485968477L, 2381948487L,
            4226929450L, 3148473363L,
            879369091L, 2180270337L,
            3674375989L, 1387729170L,
            568650985L, 951677556L,
            4213877384L, 2721005055L,
            1678669911L, 66786703L,
            2273631661L, 1149351924L,
            246723096L, 1895026827L,
            3810605772L, 3711056516L,
            2080120290L, 3638638708L,
            2915672708L, 2263003308L,
            1976115991L, 3448840877L,
            2019238520L, 225333538L,
            1555273378L, 3797521928L,
            1942347150L, 3262952567L,
            2817830907L, 2078619498L,
            749534111L, 1178073973L,
            841092198L, 3288261538L,
            1696412169L, 1496966875L,
            3739946319L, 2481012988L,
            568983526L, 114945840L,
            2841706923L, 1632780103L,
            4020169654L, 2087949619L,
            833416317L, 3787017905L,
            2373238993L, 2575395164L,
            2542976862L, 2971726178L,
            2880371864L, 3642087909L,
            1043714217L, 3894199764L,
            2235879182L, 203853421L,
            834683330L, 425935223L,
            3560796393L, 3565833278L,
            3414330886L, 1748785729L,
            1023171602L, 580966986L,
            2657385925L, 2124704694L,
            233442446L, 1107045577L,
            3899097693L, 1067532701L,
            115667924L, 1406028344L,
            2419657149L, 18613994L,
            2532882091L, 3476683808L,
            895961699L, 3762914298L,
            1328752423L, 1844996900L,
            1210281744L, 904215228L,
            4055325594L, 1118521573L,
            3996647489L, 3657647605L,
            325254059L, 3136157065L,
            3341068436L, 2287683323L,
            1313073005L, 126005630L,
            853746559L, 3555092974L,
            2689238752L, 49515858L,
            61073168L, 1010661841L,
            1269521335L, 1902040126L,
            3858321250L, 1400735275L,
            2974699176L, 2771676666L,
            545726212L, 2225229957L,
            1086473152L, 3454177594L,
            2088002891L, 2883475137L,
            3222194252L, 4144472319L,
            567988835L, 1051332394L,
            3932046135L, 542648229L,
            162888005L, 1669710469L,
            1492500905L, 553041029L,
            3817492747L, 584127807L,
            4147115982L, 2993670925L,
            3509733475L, 3587959456L,
            2088550465L, 1745399498L,
            869648362L, 1404723176L,
            3947542735L, 1334333531L,
            59634866L, 3239516985L,
            3844250972L, 1275954779L,
            2512155003L, 1685649437L,
            639306006L, 2524620206L,
            576786501L, 655707039L,
            2864351838L, 3736264674L,
            1200907897L, 2384379464L,
            15823708L, 206117476L,
            1193310960L, 1093099415L,
            3696538026L, 4112584792L,
            2069527017L, 547588820L,
            4178147211L, 2827259351L,
            940846775L, 1054995047L,
            2976960697L, 1934305529L,
            2199137382L, 1005722394L,
            1875867180L, 2064356511L,
            4019734130L, 3096333006L,
            2069509024L, 2906358341L,
            2232866485L, 1456016086L,
            1422674894L, 867282151L,
            1612503136L, 1739843072L,
            134947567L, 2978775774L,
            1284167756L, 1090844589L,
            831688783L, 2079216362L,
            1626991196L, 3644714163L,
            3678110059L, 898470030L,
            3916646913L, 3182422972L,
            3630426828L, 969847973L,
            3427164640L, 3463937250L,
            3044785046L, 897322257L,
            3443872170L, 4185408854L,
            2557463241L, 4080940424L,
            2048168570L, 2429169982L,
            3174690447L, 2513494106L,
            1213061732L, 3143736628L,
            3482268149L, 1250714337L,
            31648125L, 3872383625L,
            1565760579L, 36665130L,
            751041229L, 2257179590L,
            2915361862L, 280819225L,
            2907818413L, 4254297769L,
            3493178615L, 3755944354L,
            4043533423L, 1134196225L,
            4177134659L, 127246419L,
            2442615581L, 923049607L,
            1004426206L, 782768297L,
            2410586681L, 1430106871L,
            4103323427L, 3168399477L,
            3716682375L, 3616334719L,
            3413209549L, 656672786L,
            2876965944L, 182894450L,
            456581318L, 2683752067L,
            3877875910L, 3190666241L,
            3240336907L, 4024807233L,
            1681224377L, 1576191191L,
            3599250276L, 2381111980L,
            3495321877L, 3956024585L,
            1611608524L, 3815677453L,
            2062334396L, 1656117707L,
            5457134L, 3234118251L,
            470187419L, 2688566989L,
            3259870297L, 660100446L,
            442236198L, 2542452448L,
            493137955L, 392411099L,
            947967568L, 1234595917L,
            4230082284L, 2762976773L,
            2870085764L, 1455086530L,
            2762099647L, 4011882747L,
            1215981925L, 3227517889L,
            3269061963L, 4037515364L,
            3168911474L, 4255057396L,
            2026092260L, 1736192508L,
            3909727042L, 3114708966L,
            1938800693L, 680793595L,
            1525265867L, 2808224480L,
            2122290603L, 1211197714L,
            3520488321L, 3979192396L,
            3540779343L, 4192918639L,
            2736030448L, 1120335563L,
            1698949078L, 3993310631L,
            1966048551L, 2228221363L,
            597941119L, 3498018399L,
            393987327L, 454500547L,
            1222959566L, 567151340L,
            3774764786L, 1492844524L,
            3308300614L, 805568076L,
            868414882L, 177406999L,
            1608110313L, 642061169L,
            1027515771L, 3131251981L,
            2851936150L, 4272755262L,
            1532845092L, 709643652L,
            682573592L, 1244104217L,
            796769556L, 2500467040L,
            3002618826L, 1112998535L,
            1780193104L, 1243644607L,
            3691719535L, 2958853053L,
            466635014L, 2277292580L,
            4082276003L, 1030800045L,
            1750863246L, 379050598L,
            3576413281L, 731493104L,
            132259176L, 4115195437L,
            1769890695L, 2715470335L,
            1819263183L, 2028531518L,
            2154809766L, 3672399742L,
            76727603L, 4198182186L,
            2304993586L, 1666387627L,
            284366017L, 3359785538L,
            3469807328L, 2926494787L,
            3829072836L, 2493478921L,
            3738499303L, 3311304980L,
            932916545L, 2235559063L,
            2909742396L, 1765719309L,
            1456588655L, 508290328L,
            1490719640L, 3356513470L,
            2908490783L, 251085588L,
            830410677L, 3172220325L,
            3897208579L, 1940535730L,
            151909546L, 2384458112L,
    };
}
